λ¬Έμ
건μ€νμ¬μ μ€κ³μ¬μΈ μ£ λ₯΄λλ κ³ κ°μ¬λ‘λΆν° μλμ°¨ κ²½μ£Όλ‘ κ±΄μ€μ νμν 견μ μ μλ’°λ°μμ΅λλ€. μ 곡λ κ²½μ£Όλ‘ μ€κ³ λλ©΄μ λ°λ₯΄λ©΄ κ²½μ£Όλ‘ λΆμ§λ N x N ν¬κΈ°μ μ μ¬κ°ν 격μ ννμ΄λ©° κ° κ²©μλ 1 x 1 ν¬κΈ°μ λλ€. μ€κ³ λλ©΄μλ κ° κ²©μμ μΉΈμ 0 λλ 1 λ‘ μ±μμ Έ μμΌλ©°, 0μ μΉΈμ΄ λΉμ΄ μμμ 1μ ν΄λΉ μΉΈμ΄ λ²½μΌλ‘ μ±μμ Έ μμμ λνλ λλ€. κ²½μ£Όλ‘μ μΆλ°μ μ (0, 0) μΉΈ(μ’μΈ‘ μλ¨)μ΄λ©°, λμ°©μ μ (N-1, N-1) μΉΈ(μ°μΈ‘ νλ¨)μ λλ€. μ£ λ₯΄λλ μΆλ°μ μΈ (0, 0) μΉΈμμ μΆλ°ν μλμ°¨κ° λμ°©μ μΈ (N-1, N-1) μΉΈκΉμ§ 무μ¬ν λλ¬ν μ μκ² μ€κ°μ λκΈ°μ§ μλλ‘ κ²½μ£Όλ‘λ₯Ό 건μ€ν΄μΌ ν©λλ€. κ²½μ£Όλ‘λ μ, ν, μ’, μ°λ‘ μΈμ ν λ λΉ μΉΈμ μ°κ²°νμ¬ κ±΄μ€ν μ μμΌλ©°, λ²½μ΄ μλ μΉΈμλ κ²½μ£Όλ‘λ₯Ό 건μ€ν μ μμ΅λλ€. μ΄λ, μΈμ ν λ λΉ μΉΈμ μν λλ μ’μ°λ‘ μ°κ²°ν κ²½μ£Όλ‘λ₯Ό μ§μ λλ‘ λΌκ³ ν©λλ€. λν λ μ§μ λλ‘κ° μλ‘ μ§κ°μΌλ‘ λ§λλ μ§μ μ μ½λ λΌκ³ λΆλ¦ λλ€. κ±΄μ€ λΉμ©μ κ³μ°ν΄ 보λ μ§μ λλ‘ νλλ₯Ό λ§λ€ λλ 100μμ΄ μμλλ©°, μ½λλ₯Ό νλ λ§λ€ λλ 500μμ΄ μΆκ°λ‘ λλλ€. μ£ λ₯΄λλ 견μ μ μμ±μ μν΄ κ²½μ£Όλ‘λ₯Ό 건μ€νλ λ° νμν μ΅μ λΉμ©μ κ³μ°ν΄μΌ ν©λλ€.
μλ₯Ό λ€μ΄, μλ κ·Έλ¦Όμ μ§μ λλ‘ 6κ°μ μ½λ 4κ°λ‘ ꡬμ±λ μμμ κ²½μ£Όλ‘ μμμ΄λ©°, κ±΄μ€ λΉμ©μ 6 x 100 + 4 x 500 = 2600μ μ λλ€.
λ λ€λ₯Έ μλ‘, μλ κ·Έλ¦Όμ μ§μ λλ‘ 4κ°μ μ½λ 1κ°λ‘ ꡬμ±λ κ²½μ£Όλ‘μ΄λ©°, κ±΄μ€ λΉμ©μ 4 x 100 + 1 x 500 = 900μ μ λλ€.
λλ©΄μ μν(0μ λΉμ΄ μμ, 1μ λ²½)μ λνλ΄λ 2μ°¨μ λ°°μ΄ boardκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, κ²½μ£Όλ‘λ₯Ό 건μ€νλλ° νμν μ΅μ λΉμ©μ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
μ νμ¬ν
- boardλ 2μ°¨μ μ μ¬κ° λ°°μ΄λ‘ λ°°μ΄μ ν¬κΈ°λ 3 μ΄μ 25 μ΄νμ λλ€.
-
board λ°°μ΄μ κ° μμμ κ°μ 0 λλ 1 μ λλ€.
- λλ©΄μ κ°μ₯ μΌμͺ½ μλ¨ μ’νλ (0, 0)μ΄λ©°, κ°μ₯ μ°μΈ‘ νλ¨ μ’νλ (N-1, N-1) μ λλ€.
- μμμ κ° 0μ μΉΈμ΄ λΉμ΄ μμ΄ λλ‘ μ°κ²°μ΄ κ°λ₯ν¨μ 1μ μΉΈμ΄ λ²½μΌλ‘ μ±μμ Έ μμ΄ λλ‘ μ°κ²°μ΄ λΆκ°λ₯ν¨μ λνλ λλ€.
- boardλ νμ μΆλ°μ μμ λμ°©μ κΉμ§ κ²½μ£Όλ‘λ₯Ό 건μ€ν μ μλ ννλ‘ μ£Όμ΄μ§λλ€.
- μΆλ°μ κ³Ό λμ°©μ μΉΈμ μμμ κ°μ νμ 0μΌλ‘ μ£Όμ΄μ§λλ€.
μ μΆλ ₯ μ
| board | result |
|---|---|
| [0,0,0],[0,0,0],[0,0,0] | 900 |
| [0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0] | 3800 |
| [0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0] | 2100 |
| [0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[0,1,0,0,0,1],[0,0,0,0,0,0] | 3200 |
π Logic
private void dfs(int[][] board, int prevDir, int x, int y) {
if (x == n - 1 && y == n - 1) {
minCost = Math.min(costs[x][y], minCost);
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + xDir[i];
int ny = y + yDir[i];
if (nx == 0 && ny == 0) continue;
if (!checkBoundary(nx, ny)) continue;
if (board[nx][ny] == 1) continue;
int tmp = costs[x][y];
if (prevDir != -1 && Math.abs(prevDir - i) % 2 == 1)
tmp += 500;
tmp += 100;
if ((costs[nx][ny] != 0 && costs[nx][ny] >= tmp) || costs[nx][ny] == 0) {
costs[nx][ny] = tmp;
dfs(board, i, nx, ny);
}
}
}
prevDirμ μ¬μ©ν΄ μ΄μ λ°©ν₯μ μ μ₯νκ³ , μ§μ μΈμ§ μ½λμΈμ§ νλ¨νλ€.-
νμ λ°©ν₯μ μ°μ μμλ₯Ό λκ³ , λ¨Όμ νμνλ€.
- λΉμ©μ΄ λ μμ κ²½μ°μ 건μ€λ§μ updateνλλ‘ νλ€.
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Solution {
int[] xDir = { 0, 1, 0, -1 };
int[] yDir = { 1, 0, -1, 0 };
int[][] costs;
int n;
int minCost = Integer.MAX_VALUE;
public int solution(int[][] board) {
costs = new int[board.length][board.length];
n = board.length;
dfs(board, -1, 0, 0);
return minCost;
}
private void dfs(int[][] board, int prevDir, int x, int y) {
if (x == n - 1 && y == n - 1) {
minCost = Math.min(costs[x][y], minCost);
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + xDir[i];
int ny = y + yDir[i];
if (nx == 0 && ny == 0) continue;
if (!checkBoundary(nx, ny)) continue;
if (board[nx][ny] == 1) continue;
int tmp = costs[x][y];
if (prevDir != -1 && Math.abs(prevDir - i) % 2 == 1)
tmp += 500;
tmp += 100;
if ((costs[nx][ny] != 0 && costs[nx][ny] >= tmp) || costs[nx][ny] == 0) {
costs[nx][ny] = tmp;
dfs(board, i, nx, ny);
}
}
}
private boolean checkBoundary(int x, int y) {
return (x < n && x >= 0 && y < n && y >= 0);
}
}
βοΈ Review
- μκ° μΈλ‘, κ°λ¨ν
DFSλ¬Έμ μλ€. μ΄μ λ°©ν₯μ DFSμ μΈμλ‘ μ λ¬ν΄μ£Όλ κ²μ΄ μ€μνλ κ² κ°λ€.
π μΆμ²
Programmers : https://programmers.co.kr/learn/courses/30/lessons/67259